// 有效括号
function isValid(str) {
  if (str.length % 2 === 1) return false
  let map = {
    '[': ']',
    '(': ')',
    '{': '}',
  }
  let stack = []
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
      stack.push(str[i])
    } else {
      if (str[i] !== map[stack.pop()]) return false
    }
  }
  if (stack.length) return false
  return true
}
// 对象flattern
function isObject(val) {
  return typeof val === 'object' && val !== null
}
// or
function isObject(value) {
  return Object(value) === value
}
function flatterObj(val) {
  if (!isObject(val)) return val
  let res = {}
  const dfs = (obj, prefix) => {
    if (isObject(obj)) {
      if (Array.isArray(obj)) {
        for (let i = 0; i < obj.length; i++) {
          dfs(obj[i], `${prefix}[${i}]`)
        }
      } else {
        for (let k in obj) {
          dfs(obj[k], `${prefix}${prefix ? '.' : ''}${k}`)
        }
      }
    } else {
      res[prefix] = obj
    }
  }

  dfs(val, '')
  return res
}
// jsontodom

function jsontodom(vnode) {
  if (typeof vnode === 'number') vnode = String(vnode)
  if (typeof vnode === 'string') return document.createTextNode(vnode)
  let dom = document.createElement(vnode.tag)

  if (vnode.attrs) {
    for (let k in vnode.attrs) {
      dom.setAttribute(k, vnode.attrs[k])
    }
  }

  vnode.children.forEach((child) => dom.appendChild(jsontodom(child)))
  return dom
}

// 数组公共最长前缀
// 方法1
function prefixMaxArrStr(strs) {
  if (strs.length === 0) return ''
  if (strs.length === 1) return strs[0]
  let result = ''
  let k = strs[0]
  let length = strs.length
  for (let i = 0; i < k.length; i++) {
    for (let j = 1; j < length; j++) {
      if (k[i] !== strs[j][i]) {
        return result
      }
    }
    result += k[i]
  }

  return result
}

// 方法2
// 方法3

// 字符串的最长不重复子串
// abaaccabcdefggggg
function longestNoRepeatSubStr(string) {
  if (string.length === 0) return 0
  let left = 0
  let right = 1
  let max = 0

  while (right <= string.length) {
    let lr = string.slice(left, right)
    const index = lr.indexOf(string[right])

    if (index > -1) {
      left = index + left + 1
    } else {
      lr = string.slice(left, right + 1)
      max = Math.max(max, lr.length)
    }

    right++
  }

  return max
}
// console.log(longestNoRepeatSubStr('abaaccabcdefggggg'))

// [1,2,3,7] =>  4
// 方法1
// const firstMissingPositive = (nums) => {
//   let i = 0
//   let res = 1
//   while (i < nums.length) {
//     if (nums[i] == res) {
//       res++
//       i = 0
//     } else {
//       i++
//     }
//   }
//   return res
// }
// console.log(firstMissingPositive([3, 2, 1]))

// 方法2
// const firstMissingPositive = (nums) => {
//   const set = new Set()
//   for (let i = 0; i < nums.length; i++) {
//     set.add(nums[i])
//   }
//   for (let i = 1; i < nums.length + 1; i++) {
//     if (!set.has(i)) return i
//   }
// }

// 方法3
const firstMissingPositive = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    while (
      nums[i] >= 1 &&
      nums[i] <= nums.length && // 对1~nums.length范围内的元素进行安排
      nums[nums[i] - 1] !== nums[i] // 已经出现在理想位置的，就不用交换
    ) {
      debugger
      ;[nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]]
    }
  }
  //   console.log(nums)
  // 现在期待的是 [1,2,3,...]，如果遍历到不是放着该放的元素
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] != i + 1) {
      return i + 1
    }
  }
  return nums.length + 1 // 发现元素 1~nums.length 占满了数组，一个没缺
}

console.log(firstMissingPositive([1, 2, 3, 4, 2]))

// 从给定的数据源里，挑选 n 个元素，组成一个随机的不重复的数组，实现的方法有那些，如何优化

// 方法1：遍历的同时，就在生成的数组上进行判断重复的操作，重复就回滚 index 重新拿元素，时间复杂度最优是 O(n)，最差是 O(n2)

// 方法2：用一个hash结构来判断重复，重复就回滚重新取元素

function getNewArr(arr, n) {
  let hash = {}
  let result = []
  for (let i = 0; i < n; i++) {
    const random = Math.floor(Math.random() * arr.length)
    // if (result.indexOf(arr[random]) > -1) {
    //   // result.includes(arr[random])
    //   // result.indexOf(arr[random]) > -1
    //   i--
    //   continue
    // }
    // result.push(arr[random])
    if (!hash[arr[random]]) {
      hash[arr[random]] = 1
      result.push(arr[random])
    } else {
      i--
      continue
    }
  }
  return result
}

// 方法3：交换 这个是真的没看懂
// function getTenNum(testArray, n) {
//   const cloneArr = [...testArray]
//   let result = []
//   for (let i = 0; i < n; i++) {
//     const random = Math.floor(Math.random() * (cloneArr.length - i))
//     result.push(cloneArr[random])
//     cloneArr[random] = cloneArr[cloneArr.length - 1 - i]
//   }
//   return result
// }
// const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
// const resArr = getTenNum(testArray, 10)
// console.log(resArr)

// 方法4：边遍历边删除 这个很好理解
function getTenNum(testArr, n) {
  const cloneArr = [...testArr]
  let result = []
  for (let i = 0; i < n; i++) {
    const random = Math.floor(Math.random() * cloneArr.length)
    result.push(cloneArr[random])
    cloneArr.splice(random, 1)
  }
  return result
}

// 数组去重
// function arrRemove(arr) {
//   let result = []

//   let hash = {}

//   for (let i = 0; i < arr.length; i++) {
//     if (!hash[arr[i]]) {
//       result.push(arr[i])
//       hash[arr[i]] = 1
//     }
//   }

//   return result
// }

// function arrRemove(arr) {
//   let result = []
//   for (let i = 0; i < arr.length; i++) {
//     if (result.indexOf(arr[i]) > -1) {
//       continue
//     } else {
//       result.push(arr[i])
//     }
//   }

//   return result
// }

function arrRemove(arr) {
  return [...new Set(arr)]
}

// console.log(arrRemove([1, 2, 2, 1, 3, 4]))

// es6

// ES6 可以自定义原生数据结构（比如Array、String等）的子类，这是 ES5 无法做到的

// class 模块
// 带历史版本的 array
class VersionedArray extends Array {
  constructor() {
    super()
    this.history = [[]]
  }
  commit() {
    this.history.push(this.slice())
  }
  revert() {
    this.splice(0, this.length, ...this.history[this.history.length - 1])
  }
}

var x = new VersionedArray()

x.push(1)
x.push(2)
x // [1, 2]
x.history // [[]]

x.commit()
x.history // [[], [1, 2]]

x.push(3)
x // [1, 2, 3]
x.history // [[], [1, 2]]

x.revert()
x // [1, 2]

// 自定义 Error 子例
class ExtendableError extends Error {
  constructor(message) {
    super()
    this.message = message
    this.stack = new Error().stack
    this.name = this.constructor.name
  }
}

class MyError extends ExtendableError {
  constructor(m) {
    super(m)
  }
}

var myerror = new MyError('ll')
myerror.message // "ll"
myerror instanceof Error // true
myerror.name // "MyError"
myerror.stack
// Error
//     at MyError.ExtendableError
//     ...

// mixin 模式实现
function mix(...mixins) {
  class Mix {
    constructor() {
      for (let mixin of mixins) {
        copyProperties(this, new mixin()) // 拷贝实例属性
      }
    }
  }

  for (let mixin of mixins) {
    copyProperties(Mix, mixin) // 拷贝静态属性
    copyProperties(Mix.prototype, mixin.prototype) // 拷贝原型属性
  }

  return Mix
}

function copyProperties(target, source) {
  for (let key of Reflect.ownKeys(source)) {
    if (key !== 'constructor' && key !== 'prototype' && key !== 'name') {
      let desc = Object.getOwnPropertyDescriptor(source, key)
      Object.defineProperty(target, key, desc)
    }
  }
}
// 使用方法
class DistributedEdit extends mix(Loggable, Serializable) {
  // ...
}

// 严格模式
// 类和模块的内部，默认就是严格模式，所以不需要使用use strict指定运行模式。
// 只要你的代码写在类或模块之中，就只有严格模式可用。
// 考虑到未来所有的代码，其实都是运行在模块之中，所以 ES6 实际上把整个语言升级到了严格模式。

// class 绑定this 除了 箭头函数 constructor中调用bind方法 实例.方法 还可以用下面 Proxy + Reflect
function selfish(target) {
  const cache = new WeakMap()
  const handler = {
    get(target, key) {
      const value = Reflect.get(target, key)
      if (typeof value !== 'function') {
        return value
      }
      if (!cache.has(value)) {
        cache.set(value, value.bind(target))
      }
      return cache.get(value)
    },
  }
  const proxy = new Proxy(target, handler)
  return proxy
}

const logger = selfish(new Logger())

// class static 行为的模拟
// 静态方法 静态属性

// 静态块 解决 在外部声明或者内部声明的话每次生成一个实例都要执行一次的问题

// 私有方法 私有属性

// new.target 确定构造函数的调用方法，可以拦截非构造的调用，也可以做一个只能继承后才能实例化的 class
// 自身无法实例化，但是可以继承后，实例化子类
class Shape {
  constructor() {
    if (new.target === Shape) {
      throw new Error('本类不能实例化')
    }
  }
}

class Rectangle extends Shape {
  constructor(length, width) {
    super()
    // ...
  }
}

var x = new Shape() // 报错
var y = new Rectangle(3, 4) // 正确

// with 语句 eval 语句

// 位运算

// Object
// 这三个部署了不一样的行为
// Array.prototype.toLocaleString()
// Number.prototype.toLocaleString()
// Date.prototype.toLocaleString()

// 对象的 拷贝
var extend = function (to, from) {
  for (var property in from) {
    if (!from.hasOwnProperty(property)) continue
    Object.defineProperty(
      to,
      property,
      Object.getOwnPropertyDescriptor(from, property)
    )
  }

  return to
}
// class 模块的继承 与 Object 的继承

// JSON 对象

// JSON.stringify(obj, function|Array, number|string)
//               object array|function 空格数|'\t'之类的增加可读性

// JSON.stringify 默认会调用 对象的 toJSON 方法
// JSON.parse(jsonString, function)
//       符合json格式的字符串  处理函数，类似于JSON.stringify

// String
// // es6
// String.fromCodePoint()
// String.prototype.codePointAt()

// String.raw()

// String.prototype.normalize() // 这个方法好冷门

// String.prototype.includes()
// String.prototype.startsWith()
// String.prototype.endsWith()

// String.prototype.repeat()

// String.prototype.padStart()
// String.prototype.padEnd()

// String.prototype.trimStart() / String.prototype.trimLeft()
// String.prototype.trimEnd() / String.prototype.trimRight()

// String.prototype.matchAll()
// String.prototype.replaceAll()

// // es5
// String.fromCharCode()
// String.prototype.charCodeAt()
// String.prototype.charAt()

// String.prototype.slice() // 推荐
// String.prototype.substr() // 第二个参数规定返回的子串长度
// String.prototype.concat()
// String.prototype.substring() // 不推荐
// String.prototype.indexOf()
// String.prototype.lastIndexOf()
// String.prototype.trim()
// // 常用
// String.prototype.match()
// String.prototype.search()
// String.prototype.replace()
// String.prototype.split()

// String.prototype.localeCompare()
// String.prototype.toLowerCase()
// String.prototype.toUpperCase()
// String.prototype.toLocaleLowerCase()
// String.prototype.toLocaleUpperCase()

// // 覆盖 Object.prototype.toString() Object.prototype.valueOf()
// String.prototype.toString()
// String.prototype.valueOf()

// 函数模块
// function 尾递归优化 函数柯里化 λ演算
// 尾调用优化 尾递归优化 执行帧 执行栈
// 柯里化与递归没关系，只是包装了后，写法不一样
// 递归的本质是循环，函数式编程里没有循环，只能依赖参数计算
// 递归 优化为 尾递归 或者 优化为 循环
// 尾递归出现多参数函数可以用柯里化包装
// λ 演算 与 函数柯里化 管道机制（pipeline）即前一个函数的输出是后一个函数的输入
// 严格模式 才有 尾调用优化
// 尾递归优化的实现
// 复杂度 O(n)
function factorial(n) {
  if (n === 1) return 1
  return n * factorial(n - 1)
}
factorial(5)
// O(1)
function tailFactorial(n, total) {
  if (n === 1) return total
  return tailFactorial(n - 1, n * total)
}
// factorial(5, 1)

function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n)
  }
}
const factorial = currying(tailFactorial, 1)
factorial(5)
// 不用柯里化的话，用es6参数默认值
function factorial(n, total = 1) {
  if (n === 1) return total
  return factorial(n, n * total)
}
factorial(5)

function Fibonacci(n) {
  if (n <= 1) return 1
  return Fibonacci(n - 1) + Fibonacci(n - 2)
}

function Fibonacci(n, ac1 = 1, ac2 = 1) {
  if (n <= 1) return ac2
  return Fibonacci(n - 1, ac2, ac1 + ac2)
}
// 尾递归优化
function tco(f) {
  let value
  let accumlatored = []
  let active = false
  return function acculator() {
    accumlatored.push(arguments)
    if (!active) {
      active = true
      while (accumlatored.length) {
        value = f.apply(this, accumlatored.shift())
      }
      active = false
      return value
    }
  }
}

let sum = tco(function (x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  } else {
    return x
  }
})

console.log(sum(1, 100000))
